//
//  STLContainers.hpp
//  learnC++
//
//  Created by liuzhibing on 2018/7/1.
//  Copyright © 2018年 yunfan.com. All rights reserved.
//

#ifndef STLContainers_hpp
#define STLContainers_hpp

#include <stdio.h>
#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

class STLContainers {
    
public:
    STLContainers(){
        
    }
    
    ~STLContainers(){
        
    }
    
    void TestVector(){
        vector<int> vect;
        for (int nCount=0; nCount < 6; nCount++)
            vect.push_back(10 - nCount); // insert at end of array
        
        vect.push_back(-1);
        
        for (int nIndex=0; nIndex < vect.size(); nIndex++)
            cout << vect[nIndex] << " ";
        
        //排序
//        sort(vect.begin(), vect.end());

        vector<int>::const_iterator it; // declare an iterator
//        for (it = vect.begin(); it != vect.end(); it++) // for loop with iterators
//            cout << *it << " ";
        
        //反转
        reverse(vect.begin(), vect.end());
        
        for (it = vect.begin(); it != vect.end(); ++it) {
            cout << *it << " ";
        }
        
        
        vector<int>::const_reverse_iterator itr;
        itr = vect.rbegin();
        
//        vect.insert(vect.begin()+2, 3);//插入元素
//        
//        for (int nIndex=0; nIndex < vect.size(); nIndex++)
//            cout << vect[nIndex] << " ";
//
//
//        cout << endl;
//        连续存储结构，每个元素在内存上是连续的；
//        支持高效的随机访问和在尾端插入/删除操作，但其他位置的插入/删除操作效率低下；
        

    }
    
    void TestDeque(){
        deque<int> deq;
        for (int i = 0; i < 3; ++i) {
            deq.push_back(i);
            deq.push_front(i);
        }
        
        for (int nIndex=0; nIndex < deq.size(); nIndex++)
            cout << deq[nIndex] << " ";
        
//        连续存储结构，即其每个元素在内存上也是连续的，类似于vector，不同之处在于，deque提供了两级数组结构，第一级完全类似于vector，代表实际容器；另一级维护容器的首位地址。
//        这样，deque除了具有vector的所有功能外，还支持高效的首端插入/删除操作。
        
    }
    
    void TestList(){
        
        std::list<int> list;
        
        int i = 1;
        list.push_front(i);
        list.push_back(2);
        list.push_back(3);
//        list.pop_back();
//        list.pop_front();
        
        //第1中方法耗时最长，原因显而易见，将调用左值引用的push_back，且将会调用一次string的拷贝构造函数，比较耗时，这里的string还算很短的，如果很长的话，差异会更大
//        第2、3、4中方法耗时基本一样，参数为右值，将调用右值引用的push_back，故调用string的移动构造函数，移动构造函数耗时比拷贝构造函数少，因为不需要重新分配内存空间。
//
//        第5中方法耗时最少，因为emplace_back只调用构造函数，没有移动构造函数，也没有拷贝构造函数。
//
//        为了证实上述论断，我们自定义一个类，并在普通构造函数、拷贝构造函数、移动构造函数中打印相应描述：
        list.emplace_back(2);
        
//        非连续存储结构，具有双链表结构，每个元素维护一对前向和后向指针，因此支持前向/后向遍历。
//        支持高效的随机插入/删除操作，但随机访问效率低下，且由于需要额外维护指针，开销也比较大。
        
        std::list<int>::const_iterator it;
        
        it = min_element(list.begin(), list.end());
        cout << *it << " ";
        
        it = max_element(list.begin(), list.end());
        cout << *it << " ";
        
        //find
        std::list<int>::iterator it2;
//        在[first,last)范围内查找第一个与val相等的元素，并返回这个元素的迭代器（iterator），如果没有找到，则返回last。
        it2 = find(list.begin(), list.end(), 1);
        
        list.insert(it, 8);//use list::insert to insert the value 8 before it
        for (std::list<int>::iterator temp = list.begin(); temp != list.end(); ++temp) {
            cout << *temp << " ";
        }
        
//        请注意，sort（）在list容器类上不起作用 - list类提供了自己的sort（）成员函数，它比通用版本更有效率。
        
    }
    
    void TestSet(){
        std::set<int> set;
        
        set.insert(10);
        set.erase(0);
//        快速查找，不允许重复值
        std::set<int>::const_iterator it; // declare an iterator
        it = set.begin(); // assign it to the start of the set
        while (it != set.end()) // while it hasn't reach the end
        {
            cout << *it << " "; // print the value of the element it points to
            ++it; // and iterate to the next element
        }
        
    }
    
    void TestQueue(){
        
        std::queue<int> queue;
        
        queue.push(10);
        
        queue.pop();
        
//        std::queue: 模板类queue定义在<queue>头文件中。队列(Queue)是一个容器适配器(Container adaptor)类型，被特别设计用来运行于FIFO(First-in first-out)场景，在该场景中，只能从容器一端添加(Insert)元素，而在另一端提取(Extract)元素。只能从容器”后面”压进(Push)元素,从容器”前面”提取(Pop)元素。用来实现队列的底层容器必须满足顺序容器的所有必要条件。
    }
    
    void TestIterator(){
        vector<int> ivec(10,1);
        
        for (vector<int>::iterator iter=ivec.begin() ; iter != ivec.end(); ++iter) {
            *iter = 2;//使用 * 访问迭代器所指向的元素
        }
        
        for (vector<int>::const_iterator civec = ivec.begin() ; civec != ivec.end(); ++civec) {
            cout<<*civec;
            //*citer=3; error
//        const_iterator:
//            只能读取容器中的元素，而不能修改。
            
        }
        //        (3) iterator的算术操作：
        //        iterator除了进行++,--操作，可以将iter+n,iter-n赋给一个新的iteraor对象。还可以使用一个iterator减去另外一个iterator.
        //        const vector<int>::iterator newiter=ivec.begin();
        //        vector<int>::iterator newiter2=ivec.end();
        //        cout<<"\n"<<newiter2-newiter;
        //        一個很典型使用vector的STL程式:
        
    }
    
    void TestMap(){
        
        //https://www.jianshu.com/p/4ddc02a22c9b   map的基本使用
        
        map<int, std::string> mymap;
        //如果map中有了该key，则无法插入成功，可以使用[]下标操作
        mymap.insert(make_pair(4, "apple"));
        mymap.insert(make_pair(2, "orange"));
        mymap.insert(make_pair(1, "banana"));
        mymap.insert(make_pair(3, "grapes"));
        
        mymap.insert(pair<int, std::string>(8,"shhs"));
//        mymap.insert(map<int, string>::value_type (6,"ccc"));
        
//        用insert函数插入数据，在数据的 插入上涉及到集合的唯一性这个概念，即当map中有这个关键字时，insert操作是插入数据不了的，但是用数组方式就不同了，它可以覆盖以前该关键字对 应的值，用程序说明
        mymap[6] = "ddd";
        //是否包含元素
        map<int, string>::iterator it2;
        it2 = mymap.find(8);
//        map.end指向的元素是容器中最后一个元素之后的元素，是一个 理论上的元素 ，实际并不存在。begin是第一个元素
        if(it2 != mymap.end())
            
            cout<<"Find, the value is "<<it2->second<<endl;
        
        else
            
            cout<<"Do not Find"<<endl;
        
        
        //删除
        //1、使用迭代器
//        it2 = mymap.find(1);
//        if (it2 != mymap.end()) {
//            mymap.erase(it2);
//        }
        
        //用关键字删除
//        int n = mymap.erase(1);//如果删除了会返回1，否则返回0
        
        //用迭代器，清空
        //成片删除要注意的是，也是STL的特性，删除区间是一个前闭后开的集合
//        mymap.erase(mymap.begin(), mymap.end());
//        mymap.clear();
        
//        cout << mymap[9] << ";;:::";
        
//        if (mymap[9]) {
//            printf("suncess");
//        }else{
//            printf("fail");
//        }
        
        map<int, std::string>::const_iterator it;
        it = mymap.begin();
        while (it != mymap.end()) // while it hasn't reach the end
        {
            cout << it->first << "=" << it->second << " "; // print the value of the element it points to
            
            
            
            ++it; // and iterate to the next element
        }
        
        cout << endl;
        
        map<int, string>::reverse_iterator rit;
        rit = mymap.rbegin();
        
        //反向遍历
        for (rit = mymap.rbegin(); rit != mymap.rend(); ++rit) {
            cout<< rit->first <<"  "<< rit->second << endl;
        }
        
        //大小
        int size = mymap.size();
        
        
//        迭代器提供了一种简单的方法来逐步执行容器类的元素，而无需了解容器类的实现方式。 当与STL的算法和容器类的成员函数结合使用时，迭代器变得更加强大。 在下一课中，您将看到一个使用迭代器将元素插入列表的示例（它不提供重载操作符[]以直接访问其元素）。
        
//        有一点值得注意：迭代器必须在每个类的基础上实现，因为迭代器确实需要知道类是如何实现的。 因此迭代器总是绑定到特定的容器类。
        
    }
    
};


//迭代器的使用

class Book {
public:
    Book(){}
    Book( const char* name ){ book_name_ = name; }
    
    friend std::ostream& operator<<( std::ostream& os, const Book& book );
    
private:
    std::string book_name_;
};


class Shelf {
public:
    Shelf() {}
public:
    typedef std::vector<Book>::iterator iter;
    
    iter begin()  { return shelf_.begin(); }
    iter end()  { return shelf_.end(); }
    
    std::vector<Book> get_shelf() const { return shelf_; }
    
    void push_back( Book& book ){
        shelf_.push_back( book );
    }
    
private:
    std::vector<Book> shelf_;
};

typedef void (*callback)( Book& );
void traverse( std::vector<Book>& shelf, callback visit );

void traverse1( Shelf::iter b, Shelf::iter e, callback visit );

void visit(Book& book);

/*
 Book book1 = "C++";
 Book book2 = "Java.";
 Book book3 = "Python";
 
 Shelf shelf;
 shelf.push_back( book1 );
 shelf.push_back( book2 );
 shelf.push_back( book3 );
 
 std::vector<Book> books = shelf.get_shelf();
 traverse( books, visit );
 
 traverse1( shelf.begin(), shelf.end(), visit );
 
 说说上面的代码，我的目的是为了遍历shelf里面的book，那么问题来了。
 为什么不把遍历方法写在Shelf里面？
 作为类的设计者，无法了解过多的应用场景，只能是提供最基本的接口。比如对于Shelf的遍历可能有很多种，输出所有元素，输出所有元素+逗号，输出所有元素+\ ……所有，遍历的场景可能有很多，这个不应该由类的设计者来提供。所以，不能写在类的里面。
 
 既然不使用迭代器可以遍历，那么为什么还要使用迭代器遍历
 先说一个从文章开始处的链接中学到的东西，对于非迭代器遍历的方法，traverse需要知道shelf_的类型，那么如果现在不用vector< Book >去实现，而是换成了list< Book >，那么类的使用者需要该这里的参数类型，相当于向类的使用者暴露了过多的内部信息。其实，我觉得这个还倒是其次，这么做没有屏蔽实现的细节，通常情况下，类的使用者是不需要关注类的实现细节的，所以这么做不好。
 
 为什么迭代器遍历的方式好？
 有了上文的分析，就很容易看出，及时Shelf的设计换成了list< Book >，遍历的接口也任然不需要修改，因为迭代器类型屏蔽了底层实现的机制，用户只需专注怎么更好的使用即可。
 
 
 map的基本操作函数：
 
 C++ maps是一种关联式容器，包含“关键字/值”对
 
 begin()         返回指向map头部的迭代器
 
 clear(）        删除所有元素
 
 count()         返回指定元素出现的次数
 
 empty()         如果map为空则返回true
 
 end()           返回指向map末尾的迭代器
 
 equal_range()   返回特殊条目的迭代器对
 
 erase()         删除一个元素
 
 find()          查找一个元素
 
 get_allocator() 返回map的配置器
 
 insert()        插入元素
 
 key_comp()      返回比较元素key的函数
 
 lower_bound()   返回键值>=给定元素的第一个位置
 
 max_size()      返回可以容纳的最大元素个数
 
 rbegin()        返回一个指向map尾部的逆向迭代器
 
 rend()          返回一个指向map头部的逆向迭代器
 
 size()          返回map中元素的个数
 
 swap()           交换两个map
 
 upper_bound()    返回键值>给定元素的第一个位置
 
 value_comp()     返回比较元素value的函数
 */


#endif /* STLContainers_hpp */
